/*
题目链接:https://leetcode.cn/problems/longest-cycle-in-a-graph/description/?envType=daily-question&envId=2025-03-29
*/
//题解代码:

class Solution {
public:
    #define N 100005
    int father[N];
    int sz[N];
    void build(int n){
        for(int i=0;i<n;++i){
            father[i] = i;
            sz[i] = 1;
        }
    }
    int Find(int x){
        return x==father[x] ? x : father[x] = Find(father[x]);
    }
    void Union(int x,int y){
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy){
            father[fx] = fy;
            sz[fy] += sz[fx];
        }
    }
    int longestCycle(vector<int>& edges) {
        int n = edges.size(), ans = -1;
        build(n);
        vector<int> indegree(n);
        for(int i=0;i<n;++i){
            if(edges[i]>=0)indegree[edges[i]]++;
        }
        queue<int> q;
        for(int i=0;i<n;++i){
            if(indegree[i] == 0) q.push(i);
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            int v = edges[u];
            if(v==-1) continue;
            if(--indegree[v] == 0) q.push(v);
        }
        for(int i=0;i<n;++i){
            if(edges[i]>=0 && indegree[i] && indegree[edges[i]]) Union(i,edges[i]);
        }
        for(int i=0;i<n;++i){
            if(indegree[i]) ans = max(ans,sz[Find(i)]);
        }
        return ans;
    }
};
